package org.raymond.iworks.study.basic.algorithm.common;

/**
 * 程序员常用10种算法
 * 二分查找算法(非递归)
 * 1) 二分查找法只适用于从有序的数列中进行查找(比如数字和字母等),将数列排序后再进行查找
 * 2) 二分查找法的运行时间为对数时间O(log2n),即查找到需要的目标位置最多只需要log2n步,
 * 假设从[0,99]的队列(100个数,即n=100)中寻到目标数30,则需要查找步数为log2 100,即
 * 最多需要查找7次(2^6<100<2^7)
 */
public class BinarySearchNoRecursion {
    public static void main(String[] args) {
        int[] arr = {1,3,8,10,11,67,100};

        int index = binarySearch(arr, 67);
        if(index>=0) {
            System.out.println("find:" + arr[index]);
        }else{
            System.out.println("未找到");
        }
    }

    /**
     * @param arr 待查找的数组,升序排列
     * @param target 待查找的数
     * @return
     */
    public static int binarySearch(int[] arr, int target){
        int left=0;
        int right=arr.length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(arr[mid]==target){
                return mid;
            }else if(arr[mid]>target){
                // 需要向左边查找
                right = mid-1;
            }else{
                // 需要向右边查找
                left = mid+1;
            }
        }
        return -1;
    }
}
